package cn.kuick.match5;

import java.util.ArrayList;
import java.util.List;

public class Khan {

	
	public static class Route {
		private City a;
		private City b;
		private float cost;
		private boolean isSelected;
		
		public Route(City a, City b, float cost) {
			this.a = a;
			this.b = b;
			this.cost = cost;
			this.isSelected = false;
		}
		
		public void mark() {
			this.isSelected = true;
		}
		
		public boolean isMarked() {
			return this.isSelected;
		}
		
		public float getCost() {
			return this.cost;
		}
		
		public void setCost(float cost) {
			this.cost = cost;
		}
		
		public City getCityA() {
			return this.a;
		}
		
		public City getCityB() {
			return this.b;
		}

		@Override
		public String toString() {
			return "Route [a=" + a + ", b=" + b + ", cost=" + cost + "]";
		}
	}
	
	
	public static class City {
		private int num;
		private List<Route> routes = new ArrayList<Route>();
		private boolean isSelected;
		
		public City(int num) {
			this.num = num;
			this.isSelected = false;
		}
		
		public int getNum() {
			return this.num;
		}
		
		public void addRoute(Route route) {
			this.routes.add(route);
		}
		
		public Route findCheapestRoute() {
			Route minRoute = null;
			
			for(Route route : this.routes) {
				if (route.isSelected) {
					continue;
				}
				
				if (route.getCityA().selected() && route.getCityB().selected()) {
					continue;
				}
				
				if (minRoute == null) {
					minRoute = route;
					continue;
				}
				
				if (route.cost < minRoute.cost) {
					minRoute = route;
				}
			}
			
			return minRoute;
		}
		
		public boolean selected() {
			return this.isSelected;
		}
		
		public void mark() {
			this.isSelected = true;
		}

		@Override
		public String toString() {
			return "City [num=" + num + "]";
		}
	}
	
	public static class State {
		private int count;
		private City[] citys;
		private List<Route> routes;
		
		public State(int cityCount) {
			this.count = cityCount;
			
			this.init();
		}
		
		public void init() {
			int n = this.count;
			
			this.citys = new City[n];
			
			for(int i=0; i<n; i++) {
				this.citys[i] = new City(i);
			}
			
			this.routes = new ArrayList<Route>();
		}
		
		public City getCity(int num) {
			return this.citys[num];
		}
		
		public void addRoute(Route route) {
			this.routes.add(route);
		}
		
		public List<City> getMarkCitys() {
			List<City> markCitys = new ArrayList<City>();
			
			for(City city: this.citys) {
				if (city.selected()) {
					markCitys.add(city);
				}
			}
			
			return markCitys;
		}
		
		public List<Route> getMarkRoutes() {
			List<Route> markRoutes = new ArrayList<Route>();
			
			for(Route route: this.routes) {
				if (route.isMarked()) {
					markRoutes.add(route);
				}
			}
			
			return markRoutes;
		}
		
		public float getCosts() {
			List<Route> routes = this.getMarkRoutes();
			
			float cost = 0;
			
			for(Route route: routes) {
				cost += route.getCost();
			}
			
			return cost;
		}
		
		public static class Builder {
			
			public static class RouteConfig {
				public int numA;
				public int numB;
				public float cost;
				
				public RouteConfig(int numA, int numB, float cost) {
					super();
					this.numA = numA;
					this.numB = numB;
					this.cost = cost;
				}
			}
			
			private int cityCount;
			private List<RouteConfig> configs;
			
			public Builder(int cityCount) {
				this.cityCount = cityCount;
				this.configs = new ArrayList<RouteConfig>();
			}
			
			public Builder addRoute(int numA, int numB, float cost) {
				this.configs.add(new RouteConfig(numA, numB, cost));
				return this;
			}
			
			public State build() {
				State state = new State(cityCount);
				
				for(RouteConfig cfg : this.configs) {
					
					City a = state.getCity(cfg.numA);
					City b = state.getCity(cfg.numB);
					
					Route route = new Route(a, b, cfg.cost);
					
					state.addRoute(route);
					
					a.addRoute(route);
					b.addRoute(route);
				}
				
				return state;
			}
		}
		
		public Route findRoute(int numA, int numB) {
			for(Route route: this.routes) {
				if (route.getCityA().getNum() == numA 
						&& route.getCityB().getNum() == numB) {
					return route;
				}
			}
			
			return null;
		}
		
		public void updateRoute(int numA, int numB, float newCost) {
			Route route = this.findRoute(numA, numB);
			
			if (route != null) {
				route.setCost(newCost);
			}
		}
	}
	
	public static class RouteMarker {
		
		public void mark(State state) {
			City a = state.getCity(0);
			a.mark();
			
			this.markNext(state);
		}
		
		
		public void markNext(State state) {
			Route minRoute = null;
			
			List<City> markCitys = state.getMarkCitys();
			
			for (City city : markCitys) {
				Route route = city.findCheapestRoute();
				
				if (route == null) {
					continue;
				}
				
				if (minRoute  == null) {
					minRoute = route;
					continue;
				}
				
				if (route.getCost() < minRoute.getCost()) {
					minRoute = route;
				}
			}
			
			if (minRoute != null) {
				City a = minRoute.getCityA();
				if (!a.selected()) {
					a.mark();
				}
				
				City b = minRoute.getCityB();
				if (!b.selected()) {
					b.mark();
				}
				
				minRoute.mark();
				
				this.markNext(state);
			}
		}
	
	}
	
	public static class RouteChange {
		public int numA;
		public int numB;
		public float cost;
		
		public RouteChange(int numA, int numB, float cost) {
			super();
			this.numA = numA;
			this.numB = numB;
			this.cost = cost;
		}
	}
	
	public static float costForChange(State.Builder builder, int numA, int numB, float newCost) {
		State state = builder.build();
		
		state.updateRoute(numA, numB, newCost);
		
		RouteMarker marker = new RouteMarker();
		marker.mark(state);
		
		System.out.println("state mark routes:" + state.getMarkRoutes());
		
		return state.getCosts();
	}
	
	
	public static float expectCost(State.Builder builder, List<RouteChange> changes) {
		float total = 0;
		
		for(RouteChange change : changes) {
			float cost = costForChange(builder, change.numA, change.numB, change.cost);
			System.out.println("state min cost:" + cost);
			
			total += cost;
		}
		
		return total / changes.size();
	}
	
	public static void main1(String[] args) {
		State.Builder builder = new State.Builder(3);
		
		builder.addRoute(0, 1, 3);
		builder.addRoute(0, 2, 2);
		builder.addRoute(1, 2, 5);
		
		List<RouteChange> changes = new ArrayList<RouteChange>();
		changes.add(new RouteChange(0, 2, 3));
		changes.add(new RouteChange(1, 2, 6));
		changes.add(new RouteChange(0, 1, 6));
		
		float cost = expectCost(builder, changes);
		System.out.println("state expect cost:" + cost);
	}

	public static void main(String[] args) {
		State.Builder builder = new State.Builder(5);
		
		builder.addRoute(0, 1, 3);
		builder.addRoute(0, 2, 2);
		builder.addRoute(0, 3, 5);
		builder.addRoute(1, 2, 5);
		builder.addRoute(2, 3, 2);
		
		List<RouteChange> changes = new ArrayList<RouteChange>();
		changes.add(new RouteChange(0, 2, 3));
		changes.add(new RouteChange(1, 2, 6));
		changes.add(new RouteChange(0, 1, 5));
		
		float cost = expectCost(builder, changes);
		System.out.println("state expect cost:" + cost);
	}
	
}
